package middle;

import java.util.HashMap;
import java.util.Map;

public class Solution_106 {

    private final Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map.clear();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(0, inorder.length - 1, postorder, postorder.length - 1);
    }

    public TreeNode buildTree(int inBegin, int inEnd, int[] postorder, int postEnd) {
        TreeNode node = new TreeNode(postorder[postEnd]);
        Integer index = map.get(node.val);
        int leftNum = index - inBegin;
        int rightNum = inEnd - index;
        if (leftNum > 0) {
            node.left = buildTree(inBegin, index - 1, postorder, postEnd - rightNum - 1);
        }
        if (index < inEnd) {
            node.right = buildTree(index + 1, inEnd, postorder, postEnd - 1);
        }
        return node;
    }

    public static void main(String[] args) {
        Solution_106 model = new Solution_106();
        TreeNode node = model.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println();
    }

    class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
